#include <types.h>
#include <list.h>
#include <proc.h>
#include <assert.h>
#include <stdio.h>
#include <sched.h>
#include <sched_RR.h>
#include <sched_O1.h>

static struct sched_class *sched_class;

#define MAX_RT_PRIO 100
#define MAX_PRIO 140
#define BITMAP_COLUMN (8 * sizeof(uint32_t))	//ucore中的整数长度

#define RT_TIME_SLICE 8
#define DYNAMIC_FAC 0.05

#define BITMAP_SIZE ((MAX_PRIO - 1) / BITMAP_COLUMN + 1) 	//bitmap用整数类型表示，需要几个bitmap
 
struct prio_array {
         uint32_t nr_active;	//进程总个数
         int32_t bitmap[BITMAP_SIZE];	//bitmap表
         struct run_queue queue[MAX_PRIO];	//进程队列
};

struct prio_array *active, *expired, array[2];	//定义active表和expired表

void init_proc_prio_O1(struct proc_struct *proc) {
	proc->priority = proc->static_priority;
	if (proc->static_priority < MAX_RT_PRIO) {
		proc->time_slice = RT_TIME_SLICE;
	}
	else if (proc->static_priority < MAX_PRIO) {
		proc->time_slice = RT_TIME_SLICE - DYNAMIC_FAC * proc->static_priority;
	}
	else proc->time_slice = 0;
}

void update_proc_prio_O1(struct proc_struct *proc) {	//当某个进程时间片用尽时，更新进程的优先级
	proc->sleep_avg = 5 - rand() % 10;
	int32_t bonus = 0;
	if (proc->priority >= MAX_RT_PRIO && proc->static_priority < MAX_PRIO) {
		int32_t prio = proc->static_priority + proc->sleep_avg;
		proc->priority =  prio > MAX_RT_PRIO ? prio : MAX_RT_PRIO;
  	}
}

void update_bitmap(int32_t *bitmap, uint32_t idx) {		//更新bitmap，置成1
	uint32_t index = idx / BITMAP_COLUMN;
  	uint32_t bit_index = idx % BITMAP_COLUMN;
	assert(index < BITMAP_SIZE);
  	bitmap[index] |= (1 << (BITMAP_COLUMN - 1 - bit_index));
}

void reset_bitmap(int32_t *bitmap) {	//初始化：bitmap所有项置〇
	memset(bitmap, 0, BITMAP_SIZE * sizeof(int32_t));
}

void clear_bitmap_bit(int32_t *bitmap, uint32_t idx) {		//更新bitmap，置成0
	uint32_t index = idx / BITMAP_COLUMN;
  	uint32_t bit_index = idx % BITMAP_COLUMN;
	assert(index < BITMAP_SIZE);
  	bitmap[index] &= (~(1 << (BITMAP_COLUMN - 1 - bit_index)));
}

inline uint32_t __ffs(int32_t x) {		//查找bitmap表中从高位到低位寻找第一个非0位，子函数
	int32_t idx = -1;
	__asm__("bsf %1,%0"          
         :"=r" (idx)
         :"rm" (x));
	return BITMAP_COLUMN - 1 - idx;
}

uint32_t find_first_bit(int32_t *bitmap) {		//查找bitmap表中从高位到低位寻找第一个非0位
	int i;
  	for(i = 0; i < BITMAP_SIZE; i ++) {
		if (bitmap[i]) return __ffs(bitmap[i]) + i * BITMAP_COLUMN; 
    	}
	return -1;
}

bool is_bitmap_empty(int32_t *bitmap) {		//判断某个bitmap是否为0
	int i;
  	for(i = 0; i < BITMAP_SIZE; i ++) {
		if (bitmap[i]) return 0; 
    	}
	return 1;
}

void print_bitmap(int32_t *bitmap) {	//把bitmap表打印出来
	int i;
	for (i = 0; i < BITMAP_SIZE; i ++) {
		kprintf("%0x", bitmap[i]);
	}
	kprintf("\n");
}

static void
O1_init(struct run_queue *rq) {
	sched_class = &RR_sched_class;		//为简化编程，使用了round robin算法中的函数。
    int i, j;
	for (i = 0; i < 2; i++) {
		array[i].nr_active = 0;		//把每个表的进程数置0
		memset(array[i].bitmap, 0, sizeof(array[i].bitmap));	//把bitmap置0
    	for (j = 0; j < MAX_PRIO; j++) {	
			sched_class->init(&array[i].queue[j]);	//初始化runqueue数据结构，并把runqueue的进程数置0
        	array[i].queue[j].priority = j;		//初始化每个runqueue的优先级
			array[i].queue[j].max_time_slice = 8;	//每个runqueue的最大时间片
		}
	}
	active = array;			//初始化active表
	expired = array + 1;	//初始化expired表
}

static void
O1_enqueue(struct run_queue *rq, struct proc_struct *proc) {	//enqueue
	struct prio_array *cur_prio_array = NULL;
	
	if (proc->static_priority != -1) {	//当一个进程时间片用光时，需要重新分配时间片，需要把该进程插入到expired表中
		update_proc_prio_O1(proc);
		cur_prio_array = expired;
	}
	else
		cur_prio_array = active;	//新fork出来的优先级，插入到active表中
	init_proc_prio_O1(proc);
	struct run_queue *nrq = &cur_prio_array->queue[proc->priority];	//利用优先级，找到需要插入到的runqueue

	sched_class->enqueue(nrq, proc);	//将一个进程插入到runqueue
			
	cur_prio_array->nr_active ++;	//表中进程数+1
	update_bitmap(cur_prio_array->bitmap, proc->priority);	//更新bitmap表
}

static void
O1_dequeue(struct run_queue *rq, struct proc_struct *proc) {	//dequeue
	struct run_queue *nrq = &active->queue[proc->priority];
	sched_class->dequeue(nrq, proc);	//将一个进程清除出runqueue
	
	active->nr_active --;	//表中进程数-1
	if(nrq->proc_num == 0) 
		clear_bitmap_bit(active->bitmap, proc->priority);	//更新bitmap表
}

static struct proc_struct *
O1_pick_next(struct run_queue *rq) {	//找到runqueue队列中第一个进程
    struct proc_struct *next;
    
	if (is_bitmap_empty(active->bitmap)) {	//如果active表为空，需要切换表
		if (is_bitmap_empty(expired->bitmap))	//expired表也为空，那么没有进程可以执行
			return NULL;
		else{	//否则，就切换active和expired表
			/*kprintf("current proc : %d exchange active and expired: ",current->pid);
			print_bitmap(expired->bitmap);*/
			
			struct prio_array *temp = active;
			active = expired;
			expired = temp;
			
		}
	}
	
	//查找下一个要运行的进程
    uint32_t idx = find_first_bit(active->bitmap);
	struct run_queue *nrq = &active->queue[idx];
    next = sched_class->pick_next(nrq);
    return next;
}

static void
O1_proc_tick(struct run_queue *rq, struct proc_struct *proc) {	//时间片处理
    if (proc->time_slice > 0) {
        proc->time_slice --;	
    }
    if (proc->time_slice == 0) {
        proc->need_resched = 1;
    }
}

struct sched_class O1_sched_class = {
    .name = "O1_scheduler",
    .init = O1_init,
    .enqueue = O1_enqueue,
    .dequeue = O1_dequeue,
    .pick_next = O1_pick_next,
    .proc_tick = O1_proc_tick,
};
